package com.mzy;

import java.util.Queue;
import java.util.Stack;

public class DequeLinked {


    public static class DoubleNode<V> {
        private V value;
        private DoubleNode<V> last;
        private DoubleNode<V> next;

        public DoubleNode(V value) {
            last = null;
            next = null;
            this.value = value;
        }
    }

    public static class Deque<V> {
        private DoubleNode<V> head;
        private DoubleNode<V> tail;

        private int size;


        public int size() {
            return this.size;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public void pushHead(V value) {
            // 生成数据节点
            DoubleNode<V> cur = new DoubleNode<>(value);
            // 判断是否是首次添加
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                head.last = cur;
                cur.next = head;
                head = cur;
            }
            size++;
        }

        public void pushTail(V value) {
            DoubleNode<V> cur = new DoubleNode<>(value);

            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                tail.next = cur;
                cur.last = tail;
                tail = cur;
            }
            size++;
        }

        public V popHead() {
            if (head == null) {
                return null;
            }

            V ans = head.value;
            size--;
            // 判断是否是最后一个元素
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.last = null;
            }
            return ans;
        }

        public V popTail() {
            if(tail == null) {
                return null;
            }

            V ans = tail.value;
            size--;
            if(head == tail) {
                head = null;
                tail = null;
            }else {
                tail = tail.last;
                tail.next = null;
            }
            return ans;
        }

    }

    public static void main(String[] args) {

    }
}
